package com.note.feng.leetcode.algorithms.easy.tree;

public class NineHundredThrityEight {
    /**
     * 938 二叉搜索树的范围和
     */
    /**
     * 解法：中序遍历
     * @param root
     * @param low
     * @param high
     * @return
     */
    int sum = 0;
    public int rangeSumBST(TreeNode root, int low, int high) {
        dfs(root, low, high);
        return sum;
    }

    private void dfs(TreeNode node, int low, int high){
        if(node == null){
            return ;
        }
        dfs(node.left, low, high);
        if(node.val >= low && node.val <= high){
            sum += node.val;
        }
        if(node.val > high){
            return;
        }
        dfs(node.right, low, high);

    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
